package com.wellsfargo.bm;

public class Operations {

	private long[] getBigIntegerArray(String s){
		int len=s.length();
		long[] A=new long[len];
		for(int i=0;i<len;i++){
			A[i]=(int)(s.charAt(i)-'0');
		}
		return A;
	}

	private long[] getBigIntegerArray(String s,int block){
		int len=s.length();
		int arrlen=len/block+1;
		if(len%block==0)
			arrlen--;
		long[] A=new long[arrlen];
		int i;
		for(i=0;i<arrlen-1;i++){
			A[arrlen-i-1]=Integer.parseInt(s.substring(len-block*(i+1),len-block*(i)));
		}
		A[0]=Integer.parseInt(s.substring(0, len-block*i));
		return A;
	}

	private void reverseArray(long[] A){
		int len=A.length;
		for(int i=0;i<len/2;i++){
			long temp=A[i];
			A[i]=A[len-i-1];
			A[len-i-1]=temp;
		}
	}

	private StringBuilder removeLeadingZeros(long[] prod){
		StringBuilder sb=new StringBuilder();
		boolean check=false;
		for(int i=0;i<prod.length;i++){
			if(prod[i]!=0)
				check=true;
			if(check)
				sb.append(prod[i]);
		}
		return sb;
	}

	private void appendLeadingZeros(StringBuilder S1, StringBuilder S2) {
		int numZeros=0;
		int len1=S1.length();
		int len2=S2.length();
		numZeros=len1-len2;
		StringBuilder zeros=new StringBuilder();
		for(int i=0;i<Math.abs(numZeros);i++)
			zeros.append('0');
		if(len1>len2)S2.insert(0, zeros);
		else S1.insert(0, zeros);
	}
	public StringBuilder bigIntegerAdd(String S1, String S2){
		StringBuilder s1=new StringBuilder(S1);
		StringBuilder s2=new StringBuilder(S2);
		appendLeadingZeros(s1,s2);
		long[] A1=getBigIntegerArray(s1.toString());
		long[] A2=getBigIntegerArray(s2.toString());
		reverseArray(A1);
		reverseArray(A2);
		int len=A1.length;

		long[] sum=new long[len+1];
		for(int i=0;i<len;i++){
			sum[i]=sum[i]+A1[i] + A2[i];
		}
		long carry=0;
		for(int i=0;i<sum.length;i++){
			long temp=(sum[i]+carry)/10;
			sum[i]=(sum[i]+carry)%10;
			carry=temp;
		}
		reverseArray(sum);
		return removeLeadingZeros(sum);
	}
	public String bigIntegerMult(String S1, String S2){
		long[] A1=getBigIntegerArray(S1);
		long[] A2=getBigIntegerArray(S2);
		reverseArray(A1);
		reverseArray(A2);
		int len1=A1.length;
		int len2=A2.length;

		long[] prod=new long[len1+len2+1];
		for(int i=0;i<len1;i++){
			for(int j=0;j<len2;j++){
				prod[i+j]=prod[i+j]+A1[i]*A2[j];
			}
		}
		long carry=0;
		for(int i=0;i<prod.length;i++){
			long temp=(prod[i]+carry)/10;
			prod[i]=(prod[i]+carry)%10;
			carry=temp;
		}
		reverseArray(prod);
		return removeLeadingZeros(prod).toString();
	}

	public String bigIntegerMultBlock(String S1, String S2,int blockSize){
		long[] A1=getBigIntegerArray(S1,blockSize);
		long[] A2=getBigIntegerArray(S2,blockSize);
		reverseArray(A1);
		reverseArray(A2);
		int len1=A1.length;
		int len2=A2.length;

		long[] prod=new long[len1+len2+1];
		for(int i=0;i<len1;i++){
			for(int j=0;j<len2;j++){
				prod[i+j]=prod[i+j]+A1[i]*A2[j];
			}
		}
		long carry=0;
		long prevmul=1;
		long curmul=1;
		long divisor=(int)Math.pow(10, blockSize);
		for(int i=0;i<prod.length;i++){
			long temp=(prod[i]+carry)/divisor;
			prod[i]=(prod[i]+carry)%divisor;
			//this is necessary because on division we may need to store 0x but instead
			// only x is stored. we add the zero in the next block.
			if(blockSize>1 && prod[i]<divisor/10)
				curmul=10;
			else
				curmul=1;
			prod[i]*=prevmul;
			prevmul=curmul;
			carry=temp;
		}
		reverseArray(prod);
		return removeLeadingZeros(prod).toString();
	}

	public void testbigIntegerMult(){
		String S1="245";
		String S2="47";
		System.out.println(bigIntegerMult(S1,S2));
	}

	public void testbigIntegerMultBlock(){
		String S1="82482485312823572828467458933024636";
		String S2="2352552257485903464856";
		System.out.println(bigIntegerMult(S1,S2));
		System.out.println(bigIntegerMultBlock(S1,S2,3));
		System.out.println(bigIntegerMultBlock(S1,S2,5));
		System.out.println(bigIntegerMultBlock(S1,S2,7));
		System.out.println(bigIntegerMultBlock(S1,S2,9));
	}

	public String bigIntegerMultKaratsuba(String S1, String S2, int block){
		StringBuilder s1=new StringBuilder(S1);
		StringBuilder s2=new StringBuilder(S2);
		appendLeadingZeros(s1,s2);
		
		long[] prod=new long[s1.length()*2+1];
		bigIntegerMultKaratsuba(s1,s2,prod,0,block);
		long carry=0;
		for(int i=0;i<prod.length;i++){
			long temp=(prod[i]+carry)/10;
			prod[i]=(prod[i]+carry)%10;
			carry=temp;
		}
		reverseArray(prod);
		return removeLeadingZeros(prod).toString();
	}
	public void bigIntegerMultKaratsuba(StringBuilder S1, StringBuilder S2, long[] prod, int endPos, int block){
		try{
			if(Integer.parseInt(S2.toString())==0)
				return;
		}
		catch(Exception e){
			
		}
		try{
			if(Integer.parseInt(S2.toString())==0)
				return;
		}
		catch(Exception e){
			
		}
		finally{

			if(Math.max(S1.length(), S2.length())==block){
				prod[endPos]=prod[endPos]+Integer.parseInt(S1.toString())*Integer.parseInt(S2.toString());
				return;
			}
			int len=S1.length();
			int N=len/2;
			StringBuilder a=new StringBuilder(S1.substring(0,N));
			StringBuilder b=new StringBuilder(S1.substring(N,len));
			StringBuilder c=new StringBuilder(S2.substring(0,N));
			StringBuilder d=new StringBuilder(S2.substring(N,len));
			bigIntegerMultKaratsuba(a,c,prod,2*(len-N)+endPos,block);
			bigIntegerMultKaratsuba(b,d,prod,endPos,block);
			appendLeadingZeros(a,d);
			bigIntegerMultKaratsuba(a,d,prod,len-N+endPos,block);
			appendLeadingZeros(b,c);
			bigIntegerMultKaratsuba(b,c,prod,N+endPos,block);
			/*StringBuilder x=bigIntegerAdd(a.toString(),b.toString());
			StringBuilder y=bigIntegerAdd(c.toString(),d.toString());
			appendLeadingZeros(x,y);
			bigIntegerMultKaratsuba(x,y,prod,N+endPos,block);*/
		}

	}

	public void testbigIntegerMultKaratsuba(){
		String S1="818798768768";
		String S2="35347876876875875875";
		System.out.println(bigIntegerMult(S1,S2));
		System.out.println(bigIntegerMultKaratsuba(S1,S2,1));
		/*System.out.println(bigIntegerMultKaratsuba(S1,S2,3));
		System.out.println(bigIntegerMultKaratsuba(S1,S2,5));
		System.out.println(bigIntegerMultKaratsuba(S1,S2,7));
		System.out.println(bigIntegerMultKaratsuba(S1,S2,9));*/
	}

}
